package a00_LeetCode.Tree;

import java.util.Scanner;

/**
 * @Author quan
 * @Description 牛客网ACM模式：根据给定的字符串还原二叉树，然后再以 中序遍历的方式输出遍历结果
 * @Date 2023/3/28 16:34
 */
public class NumKY11_nowercode {
    //TreeNode定义：该节点的值，该节点的左右孩子
    private static class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;
        //构造方法
        TreeNode(char val){
            this.val = val;
        }
    }
    // main函数搭建基本框架
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()){
            //输入当前字符串
            String str = sc.nextLine();
            //将输入的字符串还原成树
            TreeNode root = treeBuildFun(str);
            //中序遍历方式输出树的遍历结果
            middleOrder(root);
        }
    }
    //中序遍历输出树的遍历结果：左根右
    private static void middleOrder(TreeNode root) {
        if(root == null){
            return;
        }
        middleOrder(root.left);
        System.out.print(root+" ");
        middleOrder(root.right);
    }
    //给出字符串，输出树的根节点
    //定义一个索引值,从0开始
    static int index = 0;
    private static TreeNode treeBuildFun(String str) {
        //字符串遍历结束的条件：当索引越界
        if(index>=str.length()){
            return null;
        }
        //取出字符串当前索引下的字符
        char c = str.charAt(index);
        //判断该字符的类型：是#还是正常的字符:如果是#表明当前节点是空节点，就不用在树中构建，直接看下一个索引的字符
        if(c == '#'){
            index++;
            return null;
        }
        //碰到的字符不是#，就要构建:将该字符作为根节点
        TreeNode root  = new TreeNode(c);
        index++;//不断更新Index的位置，取新的字符
        root.left = treeBuildFun(str);
        root.right=treeBuildFun(str);
        return root;
    }
}
